blog & blog theme🤘 (basic template from http://xudailong.github.io) https://gaoyakun.github.io/ Thu, 18 Apr 2019 03:14:25 +0000 Thu, 18 Apr 2019 03:14:25 +0000 Jekyll v3.7.4   树状数组（Binary Indexed Tree）也叫二叉索引数。它类似于线段树，主要用于查询数组中任意区间的元素和。 Thu, 18 Apr 2019 00:00:00 +0000 https://gaoyakun.github.io/2019/04/18/binary-indexed-tree/ https://gaoyakun.github.io/2019/04/18/binary-indexed-tree/ 算法 数据结构 树状数组 数据结构   对有向无环图（DAG）进行拓扑排序，除了减治法（逐步删除入度为0的顶点）之外，还可以使用传统DFS方法，实现更为简单，其原理为，用传统DFS方法遍历DAG的过程中，顶点的出栈次序刚好和拓扑次序相反。 Sun, 28 Oct 2018 00:00:00 +0000 https://gaoyakun.github.io/2018/10/28/toplogic-sort-using-dfs/ https://gaoyakun.github.io/2018/10/28/toplogic-sort-using-dfs/ 算法 图论 拓扑排序 算法   求一组矩形覆盖面积是一类很经典的算法问题，题目一般是给定N个大小已知的矩形（可以相互覆盖），求所有矩形所覆盖的总面积。假设所有矩形能覆盖的最大范围为宽w，高h，矩形数量为n，如果使用暴力法对每个面积单位进行判断的话复杂度将达到O(nwh)，显然难以接受。对于此问题，通常使用线段树+扫描线算法，这里我们介绍如何使用kd树在O(nlogn)的时间复杂度下解决此问题。 Thu, 25 Oct 2018 00:00:00 +0000 https://gaoyakun.github.io/2018/10/25/kdtree-area/ https://gaoyakun.github.io/2018/10/25/kdtree-area/ 数据结构 KD-Tree 数据结构   线段树是在对一个线性数据结构的连续区间进行动态的修改或查询操作时应用很广范的一种数据结构，它巧妙地利用了分治原理将原本的O(N)复杂度降低到O(logN)。本文介绍了线段树的基本原理和实现方法。 Tue, 23 Oct 2018 00:00:00 +0000 https://gaoyakun.github.io/2018/10/23/interval-tree/ https://gaoyakun.github.io/2018/10/23/interval-tree/ 数据结构 线段树 数据结构